import collections
class Solution(object):
    def removeDuplicateLetters(self, s):
        """
        :type s: str
        :rtype: str
        """
        n = len(s)
        stack = collections.deque([s[0]])
        already = {s[0]}
        last_d = {}
        for i in range(n):
            last_d[s[i]] = i
        for i in range(1, n):
            if s[i] not in already:
                while stack and s[i] < stack[-1]:
                    if last_d[stack[-1]] > i:
                        node = stack.pop()
                        already.remove(node)
                    else:
                        break
                stack.append(s[i])
                already.add(s[i])
        return ''.join(stack)





data = Solution()
s = "bcabc"
print(data.removeDuplicateLetters(s))
s = "cbacdcbc"
print(data.removeDuplicateLetters(s))